The present invention generally relates to the field of data communications and processing. Specifically, the present invention relates to a method and apparatus for encoding/framing a data stream of multitone modulated signals to improve impulse burst immunity.
Digital data communications systems are commonly used to transmit and/or receive data between remote transmitting and receiving locations. A central facet of any data communications system is the reliability and integrity of the data which is being communicated. Ideally, the data which is being transmitted from the transmitting location should be identical to the data which is being received at the receiving location. Practically however, the data to the data which is being received at the receiving location. Practically however, the data which is received at the receiving location has oftentimes been corrupted with respect to the original data that was transmitted from the transmitting location. Such data communication errors may be attributed in part to one or more of the transmission equipment, the transmission medium or the receiving equipment. With respect to the transmission medium, these types of data errors are usually attributed to the less than ideal conditions associated with the particular transmission medium. An example of such a communication medium or channel is the hybrid fiber coaxial cable television network, HFC CATV.
In certain channels, such as the HFC channel, errors may be caused by noise or other interference. One type of noise is ingress or narrowband interference which typically occurs at a fixed frequency and lasts for a long time. Another type of noise is impulse or burst interference which typically occurs at unexpected times, lasts for a short period of time (e.g., several microseconds), and corrupts all tones or bands.
Multitone modulation is a signal transmission scheme which uses a number of narrow-band carriers positioned at different frequencies, all transmitting simultaneously in parallel. Each narrow band carries a fraction of the total information being transmitted. The discrete bands or sub-channels are independently modulated, and each have a carrier frequency at the center frequency of the particular band.
One type of multitone transmission scheme is discrete multitone, often referred to as DMT. In DMT, a 1.1 MHz channel is broken down into 256 sub-channels or bands, each of which is 4 KHz. Each of the sub-channels has its own carrier frequency, and the signal to noise ratio for each of the sub-channels is monitored by the DMT system to determine how many bits per signal may be carried in each of the sub-channels. Each of the sub-channels transmits a number of information bits in a single symbol or signal period. The number of bits per signal (or symbol) in a sub-channel is typically referred to as the xe2x80x9cloadingxe2x80x9d of the sub-channel. The DMT system dynamically adjusts the loading of each of the sub-channels in accordance with the noise characteristics of the sub-channel. Particularly noisy sub-channels may sometimes not be used altogether.
DMT typically has long symbol periods of 250 microseconds. As a result, DMT exhibits fairly good immunity with respect to time domain events, since the effect of a time domain event will be averaged out over the relatively long symbol period. In this way, impulse noise has less of an effect on DMT transmissions. Although the effect is reduced, there is nevertheless, still an adverse effect due to impulse noise. With respect to narrowband interference, this type of noise is typically stable and can be compensated for by adjusting the loading of the particular, affected sub-channels.
Variable Constellation Multitone (VCMT) modulation is a transmission scheme specifically designed to effectively combat the high ingress and burst impairments in cable TV channels, and also to maximize the throughput capacity of such channels. VCMT uses variable bit loading per tone, along with coding and interleaving. The tones are independently modulated from QPSK (quadrature phase shift keying) to 256-QAM (quadrature amplitude modulation), depending on the noise measured for each tone. The SNR (signal to noise ratio) across the channel is monitored for each tone, and the headend receiver accordingly instructs the upstream transmitter in the cable modem to modify the QAM constellation for each tone to maintain a desired BER (bit error rate).
VCMT also utilizes spectral shaping to reduce the frequency sidelobes of the tones, as compared with conventional multitone modulation, in order to reduce the effect of narrowband interference to only those affected tones. As with all multitone modulation schemes, VCMT utilizes long symbol periods to average the effect of burst and impulse noise. Interleaving the data over time and frequency may also be used to minimize the number of impaired tones for each user.
The VCMT nominal configuration is designed for a bandwidth of 1.6 MHz. However, the VCMT configuration may be adapted for any particular bandwidth through proper modification of the system parameters. In the case of the nominal configuration, VCMT uses the following parameters:
Code Division Multiple Access (CDMA) modulation is a multi-user access transmission scheme in which different users overlap both in frequency and in time. This is in contrast to Frequency Division Multiple Access (FDMA) in which users overlap in time, but are assigned unique frequencies, and Time Division Multiple Access (TDMA) in which users overlap in frequency, but are assigned unique timeslots. According to CDMA, each user is assigned a unique code sequence that allows the user to spread its information over the entire channel bandwidth, as opposed to particular sub-channel(s) in FDMA. Thus, signals from all users are transmitted over the entire channel. To separate out the signals for a particular user at a receiver, cross correlation is performed on the received signal using the unique user code sequence. In CDMA systems, inter-user interference is minimized using one of two possible techniques.
The first technique for minimizing inter-user interference is to modulate the user signals using an orthogonal basis of wideband functions, e.g., Walsh basis. Specifically, at a given instant in time, each user selects (according to its unique code) a different basis function from the orthogonal basis, ensuring zero cross correlation between the different users. The, basis function used by each user may be changed on a symbol by symbol basis, while still ensuring that different users use different functions. The orthogonal basis itself may be changed on a symbol by symbol basis. The result is that each user occupies the entire channel bandwidth, while user cross correlation is kept to zero. The disadvantage of this approach is that in order to build a wideband (and frequency overlapping) orthogonal basis, the user data generally needs to be time synchronized since the orthogonal base construction assumes time synchronization.
A second technique for minimizing inter-user interference which does not require that the user data be time synchronized is to modulate each symbol using a pseudo randomly selected wideband waveform, which is selected according to the unique code for each user. The wideband waveform may be generated by multiplying the user data by a pseudo random sequence, referred to as a spreading sequence. This approach minimizes inter-user interference, but does not reduce the interference to zero. However, the lower the signaling rate (baud rate) is versus its bandwidth, the lower the cross correlation will be. Thus, in CDMA the signaling rate of each user is usually much smaller than the channel bandwidth it occupies in order to make the inter-user interference manageable. Typically, a ratio of 1/100 or less is common.
The above two methods for minimizing inter-user interference may be combined, for example, when it is possible to group users, such that time synchronization exists within a group, although time synchronization may not exist across groups.
CDMA transmission is well known to those of skill in the art. A comparison between CDMA and FDMA/TDMA may be found in Proakis, xe2x80x9cDigital Communicationsxe2x80x9d, Chapter 15, which is incorporated herein by reference. Also, an example of the combination of the above two approaches for minimizing inter-user interference (i.e., combining a Walsh basis within a group and a spreading sequence across groups) may be found in TIA/EIA/IS-95 xe2x80x9cMobile Station Compatibility Standard for Dual Mode Wideband Spread Spectrum Cellular Systemxe2x80x9d, which is incorporated herein by reference.
The multitone transmission schemes described above, DMT, VCMT and CDMA, may be conceptually viewed as a two-dimensional matrix, with time as the horizontal axis and frequency as the vertical axis. In the presence of ingress (narrowband interference), in the case of CDMA, all codes are corrupted by the ingress, while in VCMT, a single row (or tone) is corrupted, and in DMT, the ingress affects primarily a single row (or tone) with a much lesser effect on adjacent rows. In the presence of impulse (burst interference), the effect on CDMA and DMT is the corruption of a single symbol, while the effect on VCMT is the corruption of primarily a single symbol.
To overcome these problems, data communications systems often rely on error detection and error correction schemes, to detect the occurrence of a data error and to correct a data error, respectively. One simple form of error detection is the use of a parity bit associated with each block of data to indicate whether the particular block contains an odd or even number of 1 bits. However, this is a very simple scheme which has numerous disadvantages. It is a simple type of error detection scheme which is capable of accurately detecting up to one bit error per data block. Moreover, the use of a parity bit cannot detect the occurrence of two bit errors in a data block, since this is not even detected as a parity violation. Additionally, the use of a parity bit only detects errors; it cannot correct errors. Any time that an error is detected, the receiving location typically requests retransmission of the particular data block from the transmitting location.
One type of error correction scheme commonly used in data communications systems is the use of redundant data transmissions and a voting circuit at the receiving location. In such a system, the data being transmitted is repeated a number of times, such as five. At the receiving location, all five data blocks are received and processed by a voting circuit which compares the five received versions of each data bit and determines the bit to be a 1 or 0 based on the voting consensus. Although such a system is capable of detecting and correcting data errors, it does so at a great cost in terms of the effective data throughput or transmission rate. This is due to the fact that each data block must be repeated a number of times.
The above-mentioned correction/detection schemes are examples of binary block codes. Specifically, an (n,k,d) binary block code is a set of 2k binary codewords of block length n and minimum distance d (i.e., coding distance). The transmitted data is partitioned into binary blocks of length k, then each block is mapped into a binary codeword of length n, which is then modulated and transmitted through the channel, or sub-channels in the case of multiple sub-channels, such as in DMT or VCMT. This block code is capable of correcting up to t=(dxe2x88x921)/2 errors within each codeword.
As mentioned above, there are cases where channel errors occur in non-frequent bursts, the length of which exceeds the error correction capability of the code. These cases are handled by interleaving the data stream before it is modulated and transmitted through the channel. Functionally, an interleaver is a memory device which is used to rearrange and separate the codewords or frames which are to be transmitted. Although certain aspects of the present invention are described by way of reference to interleavers, such as block interleavers, it should be understood that any type of interleaving, such as for example, convolutional interleaving, may be used. The terms codeword and frame are used interchangeably herein where a frame includes only one codeword. Instead of transmitting a succession of complete codewords, the interleaver allows the transmission of a portion (such as a byte) of a first codeword, followed by a portion of a second codeword, and so on. Henceforth, these portions will be referred to as either symbols or codeword symbols. In this way, if an error burst occurs during transmission, the error burst will not be localized to one particular frame. Rather, the errors will be spread across several codewords. If the errors were completely within one codeword, they may exceed the number of errors which the system can inherently correct for by the use of a block code. By spreading the data errors across several blocks, the number of errors within each block may be reduced to the point where the system is capable of correcting the data errors.
In a simple interleaver, data is written into the memory in columns and then read out in rows for subsequent transmission. At the receiver end, the received data is written into a de-interleaver in rows and then read out in columns. The interleaver rearranges the data within the codewords, and the de-interleaver essentially performs the reverse process to reconstruct the codewords for subsequent use. In this type of interleaver, all the data write operations are carried out as a group, and then the data read operations are carried out as a group. This type of interleaving, referred to as block interleaving, introduces latency of one block at the transmitter and one block at the receiver, due to the fact that a complete block has to be written before it can be read.
The present invention is for an encoding/framing scheme for multitone modulation over impulsive channels. The encoding/framing scheme allows efficient operation in multipoint to point channels which are affected by ingress (narrowband noise) and impulsive (burst) interference. The coding is achieved using a concatenated approach, with the inner code being Trellis Coded Modulation (TCM), using, for example, convolutional coding, and the outer code being a Reed Solomon (RS) code. Two dimensional interleaving is performed, with one dimension being time, and the other dimension being frequency (tones or sub-channels). In contrast to conventional coding schemes, the TCM coding provided by the present invention is quite effective in dealing with impulse noise effects. The present invention is also for a two level interleaving approach, in which different interleaving is performed on different levels. According to one embodiment of the present invention, the user data is RS encoded, and a portion of the RS encoded data is interleaved and filled along columns for transmission using a multitone transmission system. The remaining portion of the RS encoded user data is then TCM encoded, interleaved and effectively filled along rows for subsequent transmission. In another embodiment according to the present invention, a portion of the user data is RS encoded, interleaved and filled along columns for transmission, while the remaining portion of the user data is instead TCM encoded, interleaved and effectively filled along rows for subsequent transmission. The actual filling of the TCM encoded data may be performed along columns; however, the interleaving essentially introduces a reversal between columns and rows, such that the effective filling of data is along rows. In addition to the reversal of columns and rows, the interleaving also introduces time separation of symbols, which is a function of the interleaver depth.
The advantage of this approach is that the RS code symbols are filled in columns, while the TCM codewords are filled in rows. The first effect is that the number of RS bytes that are impacted by an impulse is reduced. Otherwise, an impulse could affect a larger number of RS bytes if they were filled in rows. Although the impacted RS bytes might be more severely impacted, due to the nature of the RS coding, it does not matter whether the RS byte is corrupted by one bit or by many bits. Thus, the advantage of the present invention is reducing the total number of RS bytes which contain any corrupted bits. The second effect is that the TCM codewords are filled in along rows, which in the case of an impulse, reduces the number of bits corrupted in each corrupted codeword. Again, because of the nature of the TCM coding, it is preferable to reduce the maximum number of corrupted bits likely to be experienced, in order to reduce the coding redundancy required of all codewords.
The present invention is also for a diagonalization scheme which provides immunity against impulse noise, while at the same time allowing for a simple method of utilizing tones of different loading. According to the diagonalization principle, data packets are spread over time in a diagonal fashion, such that an impulse noise affects more than one user""s packets, with the effect on each being reduced. In this way, a code having lower redundancy can be used since the amount of corruption expected in one user""s data packet will be reduced.